Okay, according to my clock, the quiz should start now.

Okay, thumbs up at things.

So, we see a relatively, we see a admissible and consistent,

and those kind of things. You've probably only looked at the abstract definitions.

And if seeing a concrete thing that needs to be admissible or consistent,

if that comes as a shock to you, that might be something you want to practice.

Okay, all of those things look good in the abstract.

What we're really about in this class is getting our hands dirty, either via programs,

or by thinking through and understanding the issues with examples.

That's exactly what we're trying to get you to do with these quiz questions.

By the way, we're working very hard to give you practice quiz questions in the future.

The functionality is not quite ready yet, but we're working hard on this.

Because the quizzes should not only be kind of a threat,

they should also be something you can practice for.

We want to support you in this.

Okay, so, yes?

Yes? That will be something you asked in the tutorial.

Or, your friends, or a question in the localized forums.

We're trying to be quite prompt in answering.

Okay, we talked about heuristic search.

The idea there is that all these breadth-first search, depth-first search, uniform-cost search,

all of those are what we call uninformed search algorithms.

Uninformed because they have only the information that is given with the search problem.

They typically behave extremely poorly for big problems,

especially for problems that have a lot of branching in the search space.

Any interesting problem has a lot of branching in the search space.

So, the next thing we did was go to informed search.

And the idea is we give ourselves a little bit more of information, a sense of smell.

And it turns out that if you have a good heuristic, like straight-line distance,

but various other things as well work, then the search trees become very skinny.

And skinny search trees are something we like because there's not a lot of choice.

And as a search algorithm, we like not a lot of choice because we don't have to worry about

keeping a big fringe or doing backtracking or something like this.

So, the big remaining problem is how do I find a good heuristic?

And one thing you should probably note is that there's not one heuristic to solve them all.

Every search problem has its own heuristics. Very annoying that.

We always have to dream up new heuristics and coming up with good heuristics is difficult.

It's an art, not a science.

And we've basically talked about the fact that if we actually look at heuristics,

which heuristic we choose actually matters quite a lot.

I've given you two heuristics. One is the misplaced tiles heuristic,

and the other one is the Manhattan distance heuristic.

And you can already see here that any heuristic in this case,

any heuristic that actually makes a real try is better than no heuristic.

And which heuristic we take makes a big difference too.

Now, how do we come up with good heuristics? How do we come up with the heuristic of misplaced tiles?

How do we come up with the heuristic of Manhattan distance?

And the answer is slightly embarrassing.

The answer is we cheat.

And we look at how difficult it will be to solve the problem with cheating.